|
NL（えぬえる、）は、計算複雑性理論における決定問題の複雑性クラスの一つである。非決定性チューリングマシンで対数規模の記憶領域を使って解ける問題がこのクラスに属する。 NL は Lを一般化したものである。L は決定性チューリングマシンでの対数領域問題のクラスである。決定性チューリングマシンは非決定性チューリングマシンに含まれるため、L も NL に含まれる。 NLは非決定性領域(NSPACE)の計算資源記法で形式的に定義でき、NL = NSPACE(log ''n'') となる。 計算複雑性理論の研究により、このクラスと他の複雑性クラスの関係が明らかとなり、必要な計算資源も明らかとなってきた。一方、アルゴリズムの研究によって、対数領域で解ける問題も明らかとなってきつつある。しかし、計算複雑性理論の他の分野と同様、NLについての重要な部分は未解決である。 NLの確率的定義（後述）を指して RL と呼ぶこともある。しかし、RLという名称はRLPという複雑性クラスの別名として使われることが多い（RLPとは、確率的チューリングマシンで対数領域と多項式時間で解ける問題のクラス）。 == NL完全問題 == ある複雑性クラスに属する最も難しい問題を指して完全問題という。直観的には、完全問題を効率的に解く方法が判っていれば、それを使ってそのクラスのあらゆる問題を解くことが出来る。すなわち、完全問題はその複雑性クラスの能力の程度を示すものである。 NL完全であることが判っている問題はいくつかある。STCON問題（有向グラフの2点間の経路の有無を問う問題）と2元充足可能性問題はNL完全である。2元充足可能性問題とは、連言標準形の論理式の各節（論理和で表される部分）が2つの変数で構成されているとき、その論理式を真とする変数値の組み合わせが存在するかどうかを問う問題である。以下にそのような論理式の例を示す。なお、~（チルダ）は「否定」を意味する。 :(''x''1 or ~''x''3) and (~''x''2 or ''x''3) and (~''x''1 or ~''x''2) 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「NL (計算複雑性理論)」の詳細全文を読む スポンサード リンク
|